% !Mode:: "TeX:UTF-8"
\chapter{系统设计与实现}

\section{引言}

在前面几章，本文深入研究了社交网络影响最大化问题中的两个关键部分，包括情绪传播模型和最优种子节点个数影响因素的研究。本章综合上述研究内容和成果，设计并实现了一个社交网络影响最大化分析系统，该系统是本文研究内容的应用与展示。接下来，本章首先介绍该系统的总体结构，以及各个模块的功能和对应的实现方法。

\section{系统概述}

\subsection{系统功能}

本系统主要是通过对用户提供的网络、信息传播历史轨迹以及信息的内容，拟合出该网络每条边对应的情绪传播概率。系统主要有如下几个功能：
\begin{enumerate}
\item 情感分类：系统对用户提供的每一条信息进行文本情感分类，并映射到五种不同的情绪中。其中，文本分类模型是通过微博数据训练好的。
\item 情绪传播模型参数估计：将用户提供的信息传播历史轨迹作为训练集，训练得到该网络情绪传播模型的参数，即每条边不同情绪的传播概率。
\item 最优种子节点个数推荐：在得到上述的情绪传播模型参数结果后，系统计算合适的影响最大化算法种子节点个数。
\item 结果展示：通过一个web界面与用户进行交互，并将分析结果以友好的形式展示给用户。
\end{enumerate}

\subsection{系统结构}

系统的整体结构设计如下图\ref{fig:system_structure}所示。由图可以看出，整个系统主要分为三个模块，包括情感分类模块、模型拟合与计算模块以及结果展示模块。每个模块分别负责不同的功能：
\begin{itemize}
\item 情感分类模块。情感分类模块包括离线预处理和在线情感分类两部分。离线预处理主要通过搜集大量微博数据，训练一个情感分类器。在线情感分类针对用户提供的每条文本，给出情感分类结果。
\item 模型拟合与计算模块。该模块是整个系统的核心模块，该模块首先根据第三章提出的情绪传播模型参数估计方法，在用户提供的网络、信息传播历史轨迹以及情感分类模块得到的结果上，通过影响最大化算法拟合出情绪传播模型的参数，即网络中每条边$(v,u)$关于每个情绪$c$的传播概率$p_{v,u}^c$。最后，根据第四章得到的影响最大化算法最优种子节点个数的研究结论，通过分析网络平均度以及传播概率的关系，给出影响最大化算法种子节点个数的推荐值。
\item 结果展示模块。该模块将模型拟合与计算模块得到的结果，通过友好的web界面展示给用户。
\end{itemize}

\begin{figure}[h!]{}
\centering
\includegraphics[width=0.8\textwidth]{figure/chap5/system_structure.png}
\caption{系统结构示意图}
\label{fig:system_structure}
\end{figure}

\section{系统设计与实现}

\subsection{情感分类模块}

中文文本情感分类通常有基于词典的方法、机器学习的方法和深度学习的方法：
\begin{itemize}
\item 基于词典的方法通常先构造一个情感词典，进一步综合到感叹词、否定词或双重否定词对情感极性或类别的影响，将一个文本映射到不同的情绪类型。
\item 基于机器学习的方法通常使用支持向量机、贝叶斯分类器或n-gram语言模型。使用以上几种方法做分类时，首先需要对文本提取特征，比较常用的特征有布尔型特征（词出现或未出现）、词频特征以及TF-IDF特征。
\item 深度学习做文本分类比较常见的模型有卷积神经网络和循环神经网络。一般来说，基于深度学习的方法需要先将每个词映射到一个词向量，然后基于词向量做分类。
\end{itemize}

基于词典的方法通常不够准确，而基于深度学习的方法需要庞大的模型且效果比机器学习的方法提升并不明显。因此，本系统使用朴素贝叶斯方法对中文文本进行情感分类。具体地，如第三章所述我们通过微博API采集了400万包含表情符的微博，并对微博中的乱码、网址图片链接等无用信息进行过滤。通过表情符将每条微博映射到对应的情感类别，得到了带标注的训练数据。我们在该训练数据集上应用朴素贝叶斯模型，得到文本情感分类器。该分类器的五分类准确率约为63.46\%。

在本系统中，我们使用该情感分类器对用户输入的每条文本信息进行情感分类，得到每条文本信息对应不同情绪的概率，即其情绪分布。举例来说，对于一条文本信息$i$，我们先将其进行分词得到词的集合$\{w_i\}$，通过训练好的朴素贝叶斯模型，我们可以得到每个词属于情绪$c_j$的概率以及该文本属于情绪$c_j$的概率。将文本关于不同情绪的概率归一化之后，我们得到文本的情绪分布，以便进行下一个模块的分析。

\subsection{模型拟合与计算模块}

本模块通过用户输入的网络和信息的历史传播轨迹，结合上个模块输出的信息情绪分布，拟合出情绪传播模型的传播概率并给出影响最大化算法种子节点个数的推荐值。该模块由两个部分组成，分别是：情绪传播模型参数拟合和影响最大化算法种子节点个数推荐。

\subsubsection{情绪传播模型参数拟合}

该部分的输入为网络、信息历史传播轨迹以及情感分类器预计算好的每条信息情绪分布。给定输入，根据算法\ref{alg:em_mic}的过程，就可以得到网络中每条边关于不同情绪的传播概率值。

一般来说，由于信息的历史传播轨迹不够充分，能通过训练得到概率的边个数不能保证。因此，在情绪传播模型拟合之后，我们使用第三章提到的优化算法对缺失的边概率进行估计。该做法的好处有三个：
\begin{enumerate}
\item 提高情绪传播模型的完整性，即估计尽可能多的边概率。
\item 提高情绪传播模型对现实信息传播过程建模的准确率。
\item 提高情绪传播模型的泛化能力，即对于没有出现过的信息，仍能较好地估计其传播过程。
\end{enumerate}

得到情绪传播模型后，用户可以对该社交网络进行更多的分析。例如预测用户新发布信息的传播轨迹和影响范围，预测用户之间的亲密关系和社团关系以及用于分析用户的心情与性格等。

\subsubsection{最优种子节点个数推荐}

根据第四章的实验发现与实验结论我们知道，影响最大化算法中最优种子节点个数于信息传播模型中的传播概率有关。随着概率的增加，最优种子节点个数会经历一个相变的过程，迅速递减到一个很小值。而该相变点的信息传播概率只与网络的平均度有关。

因此，我们根据用户输入网络的平均度近似计算最优种子节点个数在该网络中相变点对应的传播概率$p_c$。由于没有能够推算出准确的相变点传播概率计算公式，我们使用$p_c = \frac{1.0}{degree}$来作为一个近似结果，其中$degree$为网络的平均度。接着，我们计算情绪传播模型所有边传播概率的平均值$p_{avg}$。如果该平均值小于$p_c$，说明最优种子节点个数没有达到相变点，这时我们推荐一个常用的值50；如果该平均值大于$p_c$，说明最优种子节点个数已经达到相变点，这时我们推荐较小的值3。值得注意的是，第四章的研究发现达到相变点之后的最优种子节点在区间$[2,5]$内，且该个数与网络规模和网络平均度无关，是否有其他因素还需进一步探究。因此，我们取超过阈值的最优种子节点个数为最大值5。于是，最优种子节点个数推荐值$N_{seed}$的计算公式如下：
$$N_{seed} = \begin{cases} 50,& if\ p_{avg} > p_c \cr 5, &otherwise \end{cases}$$


\subsection{结果展示模块}

结果展示模块主要是以网站的形式与用户进行交互和展示。

\subsubsection{网站结构}

结果展示模块的网站结构如下图\ref{fig:web_structure}所示。整体结构分为前端和后端，其中前端进行用户交互，并将用户输入结果通过http请求发送给web服务器即后端。后端得到用户的输入之后，调用模型拟合与计算模块，得到网络的分析结果，并将该结果返回给前端。最后，前端将结果以友好的方式展示给用户。

\begin{figure}[h!]{}
\centering
\includegraphics[width=0.5\textwidth]{figure/chap5/web_structure.png}
\caption{网站结构示意图}
\label{fig:web_structure}
\end{figure}

网站使用flask作为后端框架。Flask是一个使用Python编写的微型wsgi框架，基于Werkzeug WSGI工具箱和Jinja2模板引擎。使用flask作为后端框架的好处有如下几点：
\begin{enumerate}
\item Flask是个非常轻量级的web应用框架，没有多余的不需要的拓展。我们的网站主要使用单页面进行展示，不需要数据库抽象、表单验证等额外的集成功能，因此flask恰好适合。
\item Flask使用Python作为编程语言，后台数据处理与计算方便。
\item Flask使用Jinja2作为模板引擎，定义和实现前端模板非常方便。
\item 文档齐全，这对展示模块的开发带来了很大便利。
\end{enumerate}

网站使用echarts作为图标展示的框架。正如其文档所说，Echarts是一个纯Javascript开发的图表库，底层依赖轻量级的Canvas类库 ZRender，提供直观，生动，可交互，可高度个性化定制的数据可视化图表。

\subsubsection{展示效果}

如图\ref{fig:interaction}所示，用户需要在交互界面提供节点之间连接关系的网络文件、如第三章中所述的用户发布信息的历史动作文件以及每条信息的情绪分布文件。用户上传完三个需要的文件之后，点击开始分析按钮，即可对网络进行分析。
\begin{figure}[h!]{}
\centering
\includegraphics[width=0.7\textwidth]{figure/chap5/interaction.png}
\caption{用户交互界面图}
\label{fig:interaction}
\end{figure}

分析结果给出网络示意图（图\ref{fig:orgin_graph}）以及情绪传播模型中边的不同情绪传播概率的示意图（\ref{fig:emotion_graph}）。其中在情绪网络中，每条边上可以看见不同情绪的传播概率。不同颜色的边表示不同的主导情绪，红色表示在这条边上愤怒情绪传播概率最大，黄色表示厌恶情绪传播概率最大，绿色表示高兴情绪传播概率最大，蓝色表示低落情绪传播概率最大，黑色表示恐惧情绪传播概率最大。

\begin{figure}[h!]{}
  \centering
  \begin{tabular}{cc}
  \subfigure[原始网络]{
    \label{fig:orgin_graph} %% label for first subfigure
    \includegraphics[width=0.5\textwidth]{figure/chap5/origin_graph.png}
  } &
  \subfigure[情绪网络]{
    \label{fig:emotion_graph} %% label for first subfigure
    \includegraphics[width=0.5\textwidth]{figure/chap5/emotion_graph.png}
  }
  \end{tabular}
  \caption{网络示意图}
  \label{fig:graph}
\end{figure}

最后，如下图\ref{fig:detail}所示，系统给出建议的种子节点个数。
\begin{figure}[h!]{}
\centering
\includegraphics[width=0.7\textwidth]{figure/chap5/detail.png}
\caption{最优种子个数推荐示意图}
\label{fig:detail}
\end{figure}

\section{本章小结}
本章简要介绍了基于本文研究工作的影响最大化分析系统的功能与结构，并详细阐述了系统各个模块的功能和实现，包括情感分类模块、模型拟合与计算模块以及结果展示模块。对于各个不同模块，我们详细介绍了实现原理和细节，最后给出了结果展示的示意图。
